\section{Previous work}

Most implementations process list elements in reverse order when
\texttt{:from-end} is true only when the specification requires it,
i.e., only for the functions \texttt{count} and \texttt{reduce}.

We designed a technique \cite{Durand:2015:ELS:reverse} that allows us
to always process list elements in reverse order very efficiently when
\texttt{:from-end} is true.  Since that paper contains an in-depth
description of our technique, and in order to keep the presentation
simple, in this paper, no example traverses the sequence from the
end.

\subsection{ECL and Clasp}

The sequence functions of ECL have a similar superficial structure to
ours, in that they take advantage of custom macros for managing common
aspects of many functions such as the interaction between the
\texttt{test} and \texttt{test-not} keyword arguments, the existence
of keyword arguments \texttt{start} and \texttt{end}, etc.
But these macros just provide convenient syntax for handling shared
aspects of the sequence functions.  They do not assist the compiler
with the optimization of the body of the code.

For functions for which the \commonlisp{} specification allows the
implementation to process elements from the beginning of the sequence
even when \texttt{from-end} is \emph{true}, ECL takes advantage of
this possibility.  For the \texttt{count} function applied to a list,
ECL simply reverses the list before processing the elements.

The \commonlisp{} code base of Clasp is derived from that of ECL, and
the code for the sequence functions of Clasp is the same as that of
ECL.

\subsection{CLISP}

The essence of the code of the sequence functions of CLISP are written
in \clanguage{}, which makes them highly dependent on that particular
implementation.  For that reason, in terms of previous work, CLISP is
outside the scope of this paper.  Our technique is still applicable to
CLISP, of course, since it uses only standard \commonlisp{} features.

\subsection{SBCL}

The sequence functions of \sbcl{} are implemented using a mixed
approach.

Macros are used to create special versions for the purpose of better
performance.  Transformations during compilation can replace a general
call to a sequence function by a call to a special version when
additional information is available such as when the sequence is a
specialized vector, or when some keyword argument has a particular
explicit value in the call.

Macros are also used to abstract details of combinations of values of
keyword arguments.

However, when little information is available at the call site, a call
to the general purpose function is maintained, and no particular
attempt has been made to optimize such calls.  As a result, in order
to obtain high performance with the \sbcl{} sequence functions, the
programmer has to supply additional explicit information about the
element type (in case of a vector) and explicit keyword arguments to
such calls.

\subsection{\ccl{}}

The sequence functions of \ccl{} are implemented according to the
approach where each function has a number of special versions
according to the type of the sequence and the combination of the
values of the keyword arguments.

However, the code in \ccl{} contains very few attempts at optimizing
performance.  For example, while there is an explicit test for whether
a vector to be used as a sequence is a simple array, there is no
attempt to specialize according to the element type of the vector.
